iT邦幫忙

2025 iThome 鐵人賽

DAY 22
0
自我挑戰組

從零開始學習LeetCode系列 第 22

Day 22 Remove Element

  • 分享至 

  • xImage
  •  

題目:給你一個整數陣列 nums 和一個整數 val。
請原地移除所有等於 val 的元素,並返回移除後陣列的長度。

  • 不可以建立新陣列,必須在原陣列修改
  • https://ithelp.ithome.com.tw/upload/images/20251005/20169339x1e8AWdzoP.jpg

解法一
https://ithelp.ithome.com.tw/upload/images/20251005/20169339CS5J7Ku3tV.jpg

  • 容易理解
  • 效率差

註解

  • while 迴圈:逐個檢查元素
  • 若 nums[i] == val,則移除
  • 若不是,繼續往下
  • 時間複雜度:O(n²),因為 pop() 每次都會重新搬移元素

理解

  • 就像在整理書櫃時,一本本拿起來檢查:
    (1)是舊書 → 拿掉
    (2)是新書 → 留著
    但每拿掉一本,後面的都要往前搬一格,所以比較慢

解法二
https://ithelp.ithome.com.tw/upload/images/20251005/201693390klHX2S6Z7.jpg

  • 雙指針法
  • 最推薦(順序保留、O(n))

註解

  • fast:用來遍歷整個陣列
  • slow:記錄「下一個應該保留」的位置
  • 若 nums[fast] != val,就把該值往前放
  • 結束後,slow 即為「新陣列長度」

理解

  • 想像你在篩書:
    (1)你手上有一本本書(fast)
    (2)桌子上有「要留下的那堆」(slow)
    (3)每當你看到一本不是 val 的,就放到桌上,桌子那堆往右擴一格

解法三
https://ithelp.ithome.com.tw/upload/images/20251005/201693394fmf0s5UyL.jpg

  • 交換法
  • 極快(O(n))
  • 不保留順序

註解

  • 不保留原本順序,但效率極高
  • 每當發現 val,就把它和最後一個元素交換
  • 減少實際操作次數

理解

  • 想像你在丟書:
    (1)你看到一本舊書(val)→ 直接拿「最後一本」來補這個洞
    (2)書櫃的總長度少一格
    (3)不在意順序,就不浪費時間搬書

上一篇
Day 21 Missing Number
下一篇
Day 23 Remove Duplicates from Sorted Array
系列文
從零開始學習LeetCode24
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言